By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 14, Issue 1, pp. 1-255

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

An Optimal Simulation of Counter Machines

Paul M. B. Vitányi

pp. 1-33

BibTeX  Abstract Full Text:  PDF

An Optimal Simulation of Counter Machines: The ACM Case

Paul M. B. Vitányi

pp. 34-40

BibTeX  Abstract Full Text:  PDF

On Circuit-Size Complexity and the Low Hierarchy in NP

Ker-I Ko and Uwe Schöning

pp. 41-51

BibTeX  Abstract Full Text:  PDF

The Complexity of Distributed Concurrency Control

Paris C. Kanellakis and Christos H. Papadimitriou

pp. 52-74

BibTeX  Abstract Full Text:  PDF

Unbounded Speed Variability in Distributed Communications Systems

John H. Reif and Paul G. Spirakis

pp. 75-92

BibTeX  Abstract Full Text:  PDF

Voronoi Diagram in the Laguerre Geometry and Its Applications

Hiroshi Imai, Masao Iri, and Kazuo Murota

pp. 93-105

BibTeX  Abstract Full Text:  PDF

An Efficient Formula for Linear Recurrences

Charles M. Fiduccia

pp. 106-112

BibTeX  Abstract Full Text:  PDF

Sparse Sets in : Relativizations

Stuart A. Kurtz

pp. 113-119

BibTeX  Abstract Full Text:  PDF

On Fault-Tolerant Networks for Sorting

Andrew C. Yao and F. Frances Yao

pp. 120-128

BibTeX  Abstract Full Text:  PDF

On the Expected Performance of Path Compression Algorithms

Andrew C. Yao

pp. 129-133

BibTeX  Abstract Full Text:  PDF

Finding Extremal Polygons

James E. Boyce, David P. Dobkin, Robert L. (Scot) Drysdale III, and Leo J. Guibas

pp. 134-147

BibTeX  Abstract Full Text:  PDF

Simplicity, Relativizations and Nondeterminism

José L. Balcázar

pp. 148-157

BibTeX  Abstract Full Text:  PDF

Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees

Moon-Jung Chung, Fillia Makedon, Ivan Hal Sudborough, and Jonathan Turner

pp. 158-177

BibTeX  Abstract Full Text:  PDF

Additive Complexity and Zeros of Real Polynomials

J. J. Risler

pp. 178-183

BibTeX  Abstract Full Text:  PDF

Factoring Polynomials over Algebraic Number Fields

Susan Landau

pp. 184-195

BibTeX  Abstract Full Text:  PDF

The Computational Complexity of Simultaneous Diophantine Approximation Problems

J. C. Lagarias

pp. 196-209

BibTeX  Abstract Full Text:  PDF

Arboricity and Subgraph Listing Algorithms

Norishige Chiba and Takao Nishizeki

pp. 210-223

BibTeX  Abstract Full Text:  PDF

Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs

Wen-Lian Hsu

pp. 224-231

BibTeX  Abstract Full Text:  PDF

New Data Structures for Orthogonal Range Queries

Dan E. Willard

pp. 232-253

BibTeX  Abstract Full Text:  PDF

Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Robert E. Tarjan and Mihalis Yannakakis

pp. 254-255

BibTeX  Abstract Full Text:  PDF